package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/peak-index-in-a-mountain-array'>山脉数组的峰顶索引(Peak Index in a Mountain Array)</a>
 * <p>给定一个长度为 n 的整数 山脉 数组 arr ，其中的值递增到一个 峰值元素 然后递减。</p>
 * <p>返回峰值元素的下标。</p>
 * <p>你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li></li>
 *     <li></li>
 *     <li></li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/4/28 15:19
 */
public class LC0852PeakIndexInMountainArray_M {

    static class Solution {
        public int peakIndexInMountainArray(int[] arr) {
            int left = 1;
            int right = arr.length - 2;
            while (left <= right) {
                int mid = left + ((right - left) >> 1);
                // 位于上升趋势
                if (arr[mid - 1] < arr[mid] && arr[mid + 1] > arr[mid]) {
                    left = mid + 1;
                }
                // 位于下降趋势
                else if (arr[mid - 1] > arr[mid] && arr[mid + 1] < arr[mid]) {
                    right = mid - 1;
                } else {
                    return mid;
                }

            }
            return -1;
        }

        public int peakIndexInMountainArray2(int[] arr) {
            for (int i = 1; i < arr.length - 1; i++) {
                if (arr[i] > arr[i + 1]) {
                    return i;
                }
            }
            return -1;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.peakIndexInMountainArray(new int[]{0, 1, 0}));
        System.out.println(solution.peakIndexInMountainArray(new int[]{0, 2, 1, 0}));
        System.out.println(solution.peakIndexInMountainArray(new int[]{0, 10, 5, 2}));
        System.out.println(solution.peakIndexInMountainArray(new int[]{18, 29, 38, 59, 98, 100, 99, 98, 90}));
    }
}
